Kierunek cyklu

Kierunek cyklu – pojęcie występujące przede wszystkim w matematyce dyskretnej, teorii grafów oraz w niektórych dziedzinach inżynierii elektronicznej. Odnosi się do określenia kolejności przechodzenia przez kolejne wierzchołki i krawędzie zamkniętej ścieżki (tzw. cyklu) w grafie skierowanym lub w grafie nieskierowanym. Kierunek może być podany w sposób zegarowy (clockwise) lub przeciwny do ruchu wskazówek zegara (counter‑clockwise), a w grafach skierowanych – jako zgodny lub przeciwny ze wskazaniem orientacji krawędzi.

Definicja

Niech graf G = (V, E) będzie zbiorem wierzchołków V oraz krawędzi E. Cyklem nazywamy ciąg wierzchołków (v₁, v₂, …, vₖ, v₁), w którym każda kolejna para (v_i, v_{i+1}) jest połączona krawędzią z E, przy czym v₁ = vₖ i żadne inne wierzchołki się nie powtarzają. Kierunek cyklu to:

• W grafie skierowanym – wybór kolejności, w której wszystkie krawędzie są podążane zgodnie z ich orientacją (tzw. cykl skierowany).
• W grafie nieskierowanym – przyjęcie dowolnej orientacji (zwykle określanej jako zegarowa lub przeciwnie do ruchu wskazówek zegara) w odniesieniu do płaszczyzny, na której graf jest rysowany.

Rodzaje kierunku cyklu

Cykle skierowane

W grafie skierowanym każdy cykl ma jeden z dwóch możliwych kierunków:

• Kierunek zgodny – wszystkie krawędzie są pokonywane w kierunku ich orientacji.
• Kierunek przeciwny – przynajmniej jedna krawędź jest pokonywana wbrew swojej orientacji, co w klasycznej definicji cyklu skierowanego jest niedozwolone.

Cykl spełniający pierwszy warunek nazywany jest cyklem skierowanym i odgrywa kluczową rolę w wykrywaniu silnej spójności oraz w algorytmach Tarjana i Kosaraju.

Cykle w grafach nieskierowanych

W grafie nieskierowanym

• Kierunek zgodny z ruchem wskazówek zegara – przyjmowany przy rysowaniu grafu na płaszczyźnie, gdy wszystkie krawędzie „okrążają” wierzchołki w tym samym kierunku.
• Kierunek przeciwny – analogicznie, ale w odwrotnej kolejności.

Takie oznaczenie jest użyteczne w analizie planarności grafu oraz w algorytmach wyznaczania twier i twier zewnętrznej.

Zastosowania

Kierunek cyklu znajduje praktyczne zastosowanie w wielu dziedzinach:

• Planowanie tras – w systemach nawigacyjnych oraz w robotyce określenie kierunku cyklu pozwala na optymalizację powrotów do punktu startowego.
• Projektowanie układów cyfrowych – w układach cyklicznych (np. liczniki, rejestry) kolejność przejść przez stany określa kierunek cyklu zegarowego.
• Analiza sieci społecznych – wykrywanie zamkniętych grup (tzw. społeczności) wymaga rozróżnienia kierunku relacji w grafach skierowanych.
• Teoria automatów – w maszynach Turinga oraz w automatów skończonych cykle definiują niekończące się zachowania, a ich kierunek wpływa na analizę stabilności.

Historia i rozwój

Pierwsze formalne rozważania na temat kierunku cyklu pojawiły się w pracach Leonaarda Eulera dotyczących problemu mostów w Königsbergu (1736). W XIX‑XX w. badacze tacy jak Gustav Kirchhoff i Claude Shannon rozszerzyli pojęcie na grafy prądowe, wprowadzając pojęcie orientacji krawędzi. W latach 70. i 80. XX w. rozwój algorytmów grafowych (np. DFS i BFS) umożliwił efektywne wykrywanie cykli skierowanych oraz określanie ich kierunku.

Powiązane pojęcia

• Cykl
• Graf skierowany
• Graf nieskierowany
• Planarność grafu
• Algorytm DFS
• Algorytm BFS
• Silna spójność
• Automaty
• Układy cykliczne

Przykłady

Przykład 1 – cykl skierowany w grafie społecznym

A → B → C → A
    

W powyższym grafie wszystkie krawędzie są zgodne z ich orientacją – więc kierunek cyklu jest zgodny.

Przykład 2 – cykl w grafie nieskierowanym

(1) — (2)
 |      |
(4) — (3)
    

Jeżeli przyjmujemy rysunek jako płaszczyznę, to podążanie od wierzchołka 1 → 2 → 3 → 4 → 1 jest kierunkiem zegarowym, a odwrotna kolejność – przeciwnym do ruchu wskazówek zegara.

Literatura

• J. Bang‑Jensen, G. Gutin, Digraphs: Theory, Algorithms and Applications, Springer, 2009.
• R. Diestel, Graph Theory, 5th ed., Springer, 2017.
• E. U. Cormen, C. Leiserson, R. Rivest, C. Stein, Introduction to Algorithms, 3rd ed., MIT Press, 2009.